﻿// 贪心 · 例8-国王的游戏.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
/*
链接：https://ac.nowcoder.com/acm/contest/20960/1029
来源：牛客网

国王邀请n 位大臣来玩一个有奖游戏。首先，他在自己和每个大臣在左、右手上面分别写下一个整数l 和r 。
然后，让这n 位大臣排成一排，国王站在队伍的最前面。排好队后，第i 位大臣可以获得金币数量：
排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果；换句话说，即：

国王不希望某一个大臣获得特别多的奖赏，所以他想重新安排大臣的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。
注意，国王的位置始终在队伍的最前面。
输入描述:
第一行输入一个整数n(1≦n≦103 ) 代表大臣的人数。
第二行输入两个整数
𝑙0,𝑟0(0<𝑙0,𝑟0<104) 代表国王左右手上的数字。
此后n 行，第i 行包含两个整数
𝑙𝑖,𝑟𝑖(0<𝑙𝑖,𝑟𝑖<104)代表每个大臣左右手上的数字。
输出描述:
在一行上输出一个整数，代表重新排列后，队伍中获奖赏最多的大臣所获得的金币数。
示例1
输入
复制
2
1 1
4 5
1 4
输出
复制
0
说明
如果从前到后依次为第一、二位大臣，此时：
因此，国王重新排列大臣的顺序后，队伍中获奖赏最多的大臣所获得的最少金币数为0 ，此时第二位大臣在前、第一位大臣在后。


示例2
输入
复制
3
1 1
2 3
7 4
4 6
输出
复制
2
说明
在这个样例中： 
∙按一、二、三这样排列队伍，获得奖赏最多的大臣所获得金币数为2 ；
∙按一、三、二这样排列队伍，获得奖赏最多的大臣所获得金币数为2 ；
∙按二、一、三这样排列队伍，获得奖赏最多的大臣所获得金币数为2 ；

 
∙按二、三、一这样排列队伍，获得奖赏最多的大臣所获得金币数为9 ；
∙按三、一、二这样排列队伍，获得奖赏最多的大臣所获得金币数为2 ；
∙按三、二、一这样排列队伍，获得奖赏最多的大臣所获得金币数为9 ；
因此，奖赏最多的大臣最少获得2 个金币。
*/
#include <iostream>

int main()
{
    std::cout << "Hello World!\n";
}

